#include <stdio.h>

#define RED 0
#define BLACK 1

#define RBTREE_ENTRY(name, type)        \
    struct name                         \
    {                                   \
        struct _rbtree_node *left;      \
        struct _rbtree_node *right;     \
        struct _rbtree_node *parent;    \
        unsigned char color;            \
    }                                   \


// 定义红黑树节点的数据结构
typedef struct _rbtree_node
{
    /*
        1. 节点颜色值
        2. 节点数据
        3. 节点key值
        4. 定义三个指针，分别指向左右节点和父节点
    */
    // 业务相关
    int key;
    void *value;

    // 红黑树相关
    RBTREE_ENTRY(, _rbtree_node);
   
   
} rbtree_node;

// 定义红黑树的数据结构
typedef struct _rbtree 
{
    /*
        1. 定义一个根节点ROOT
        2. 定义一个叶子节点的空节点NIL, 这里定义叶子节点为nil而不是空指针NULL的原因是：
        我们所定义的叶子节点必须具有红黑树节点的性质，易于红黑树操作时候的判断，如果使用NULL，我们就无法操作
    */
    struct _rbtree_node *root;
    struct _rbtree_node *nil;
} rbtree;


// 红黑树左旋 断3根，重新连接3根
void rbtree_left_rotate(rbtree *T, rbtree_node *x)
{
    rbtree_node *y = x->right;
    // 1. 将x节点的右指针指向y节点的左子树,需要判断y节点的左子树是否为叶子节点nil
    x->right = y->left;
    if(y->left != T->nil)
    {
        // 需将左子树的节点指向x节点
        y->left->parent = x;
    }
    // 2. 改变y节点的父指针的指向，需要判断x是否是父节点，x是其父节点的左子树还是右子树
    y->parent = x->parent;
    
    if(x->parent == T->root) // 2.1 如果x是父节点, 将y节点设置为根节点
    {
        T->root = y;
    }
    else if (x->parent->left == x) // 2.2 如果x是其父节点的左子树, 将其父节点的左指针指向y
    {
        x->parent->left = y;
    }
    else // 2.3 如果x是其父节点的右子树, 将其父节点的右指针指向y
    {
        x->parent->right = y;
    }
    // 3. 将y的左指针指向x， 将x的父指针指向y
    y->left = x;
    x->parent = y;
}


// 红黑树的右旋
void rbtree_right_rotate(rbtree *T, rbtree_node *y)
{
    // 与红黑树的左旋是逆方向的过程
    rbtree_node *x = y->left;
    // 1. 将y的左指针指向x的右子树，x的右子树节点的父指针指向y
    y->left = x->right;
    if(x->right != T->nil)
    {
        x->right->parent = y;
    }
    // 2. 将x的父指针指向y的父节点，将y的父指针指向x节点
    x->parent = y->parent;
    if(y->parent == T->root)
    {
        T->root = x;
    }
    else if (y->parent->left == y)
    {
        y->parent->left = x;
    }
    else 
    {
        y->parent->right = x;
    }
    // 将x的右指针指向y节点，将y节点的父指针指向x节点
    x->right = y;
    y->parent = x;
}

/*
    红黑树的节点插入:
*/

void rbtree_insert(rbtree *T, rbtree_node * z)
{
    // 定义两个指针，y指针永远保存x前一个指针
    rbtree_node *x = T->root;
    rbtree_node *y = T->nil;

    while(x != T->nil)
    {
        y = x;

        if(z->key > x->key) // 插入右树
        {
            x = x->right;
        }
        else if (z->key < x->key) // 插入左树
        {
            x = x->left;
        }
        else
        {
            // key值相等的情况下，视情况而定
            return;
        }
    }

    // 将z节点的父指针指向y
    z->parent = y;
    if(y == T->nil)
        T->root = z;
    else 
    {
        if(y->key > z->key)
        {
            y->left = z;
        }
        else 
        {
            y->right = z;
        }
    }

    z->left = T->nil;
    z->right = T->nil;
    z->color = RED;
    // 重新整理红黑树
    rbtree_insert_fixup(T, z);
}

void rbtree_insert_fixup(rbtree *T, rbtree_node *z)
{
    // 红黑树的特性: 如果一个节点是红节点，那么他的两个孩子都是黑色节点
    while(z->parent->color == RED)
    {
        // 如果z的父节点是z的组父节点的左子树
        if(z->parent == z->parent->parent->left)
        {
            // 保存其叔父节点
            rbtree_node *y = z->parent->parent->right;
            // 如果他的叔父节点也是红色的
            if(y->color == RED)
            {
                // 将父节点与叔父节点设置为红色，将祖父节点设置为黑色，并将当前节点设置为祖父节点便于后续的左旋右旋调整
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            }
            else 
            {
                // 如果当前节点是父节点的右子树,将当前节点设置为父节点后进行左旋
                if(z == z->parent->right)
                {
                    z = z->parent;
                    rbtree_left_rotate(T, z);
                }
                // 旋转过后当前节点就是其父节点的左子树
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rbtree_right_rotate(T, z->parent->parent);
            }
        }
        else // 如果z的父节点是z的组父节点的右子树
        {
            rbtree_node *y = z->parent->parent->left;
            if(y->color == RED)
            {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            }
            else 
            {
                if(z == z->parent->left)
                {
                    z = z->parent;
                    rbtree_right_rotate(T, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rbtree_left_rotate(T, z->parent->parent);

            }
        }
    }
    T->root->color = BLACK;
}